package day20210511;


import treenode.TreeNode;


/**
 * 剑指 Offer 55 - II. 平衡二叉树
 * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
 */
class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] a = {6,3,2,5,4,1,8,7,9,10,11,12,13};
        TreeNode root = TreeNode.CreateTree(a);
        System.out.println(solution.isBalanced(root));

    }
    private boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = recur(root.left);
        if (left == -1) {
            return -1;
        }
        int right = recur(root.right);
        if (right == -1) {
            return -1;
        }
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }


}
